#[derive(Debug)]
struct Stack<T> {
    top: Option<Box<StackNode<T>>>,
}

//为什么要这么做了？如果不用Box封装会怎么样呢？
//
//如果不用 Box 封装，rustc 编译器会报错，在 Rust 里面，rustc 默认使用栈空间，
// 但是这里的StackNode定义的时候使用了递归的数据结构，next 属性的类型是 StackNode<T>，
// 而这个类型是无法确定大小的，所有这种无法确定大小的类型，都不能保存在栈空间。所以需要使用Box来封装。
// 这样的话next的类型就是一个指向某一块堆空间的指针，而指针是可以确定大小的，因此能够保存在栈空间。
#[derive(Debug)]
struct StackNode<T> {
    val: T,
    next: Option<Box<StackNode<T>>>,
}

impl<T> StackNode<T> {
    fn new(val: T) -> StackNode<T> {
        StackNode {
            val,
            next: None,
        }
    }
}

impl<T> Stack<T> {
    fn new() -> Stack<T> {
        Stack {
            top: None,
        }
    }

    fn push(&mut self, val: T) {
        let mut node = StackNode::new(val);
        let next = self.top.take();
        node.next = next;
        self.top = Some(Box::new(node));
    }

    fn pop(&mut self) -> Option<T> {
        let val = self.top.take();
        match val {
            None => None,
            Some(mut x) => {
                self.top = x.next.take();
                Some(x.val)
            }
        }
    }
}

#[cfg(test)]
mod test {
    use crate::my_stack::Stack;

    #[test]
    fn test() {
        #[derive(PartialEq, Eq, Debug)]
        struct TestStruct {
            a: i32,
        }

        let a = TestStruct { a: 5 };
        let b = TestStruct { a: 9 };

        let mut s = Stack::<TestStruct>::new();
        assert_eq!(s.pop(), None);

        s.push(a);
        s.push(b);
        println!("{:?}", s);

        assert_eq!(s.pop(), Some(TestStruct { a: 9 }));
        assert_eq!(s.pop(), Some(TestStruct { a: 5 }));
        assert_eq!(s.pop(), None);
    }
}